package 二叉树;

import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
 */
public class _114_二叉树展开为链表 {
    public void flatten(TreeNode root) {
        helper(root);
    }

    /**
     * 高效率
     * 先取出左子树和右子树
     * 将左子树指向根节点的右子树
     * 将根节点的左子树置空
     * 将根节点下移到末尾
     * 将右子树指向 根节点的右子树
     * 将根节点的左子树置空
     *
     * @param root
     * @return
     */
    public TreeNode helper(TreeNode root) {
        if(root == null) return null;
        TreeNode leftNode = helper(root.left);
        TreeNode rightNode = helper(root.right);

        root.right = leftNode;
        root.left = null;

        TreeNode head = root;
        while (head.right!=null) head = head.right;
        head.right = rightNode;
        head.left = null;
        return root;
    }

    /**
     * 先前序遍历 ，再重构二叉树，
     * 其中 right 子指针指向链表中下一个结点，
     * 而左子指针始终为 null 。
     */
    List<TreeNode> list = new LinkedList();
    public void flatten1(TreeNode root) {
        preorderTraversal(root);
        for (int i = 0; i < list.size(); i++) {
            TreeNode node = list.get(i);
            root.left = null;
            root.right = node;

            root = root.right;
        }
    }

    public void preorderTraversal(TreeNode root) {
        if (root == null) return;

        list.add(root);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }
}
